package levelorder;

import entity.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class AverageOfLevels {
    /*
    * 637. 二叉树的层平均值
    * 给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。
    * 与实际答案相差 10(-5) 以内的答案可以被接受。
    * 树中节点数量在 [1, 104] 范围内
    * -2(31) <= Node.val <= 2(31) - 1
    * */
    public static void main(String[] args){

    }

    // 我的想法：
    public List<Double> mySolution(TreeNode root){
        ArrayList<Double> res = new ArrayList<>();
        if(root == null)
            return res;
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while (!deque.isEmpty()){
            double sum = 0;
            int len = deque.size();
            int total = len;
            while (len > 0){
                TreeNode node = deque.pop();
                sum += node.val;
                if(node.left != null) deque.add(node.left);
                if(node.right != null) deque.add(node.right);
                len--;
            }
            res.add(sum/total);
        }
        return res;
    }
}
